#include <math.h>
#include <stdlib.h>
#include <time.h>
//#include "sys.h"
#include "rsa.h"


int generate_rand(char *p, int len) {
	int i;
	//srand((unsigned)time(0));
	// srand((unsigned)GetSystemTime());	wushuai
	static int volatile seed;
	srand((unsigned int)&seed);
	for (i = 0; i < len; i++)
		switch (rand() % 3) {
		case 0:*(p + i) = 'A' + rand() % 26; break;
		case 1:*(p + i) = 'a' + rand() % 26; break;
		case 2:*(p + i) = '0' + rand() % 10; break;
		}
	return 0;
}

long long ExtEuclid(unsigned long long a, unsigned int b)
{
	unsigned long long x = 0, y = 1, u = 1, v = 0, gcd = b, m, n, q, r;
	while (a != 0) {
		q = gcd / a;
		r = (gcd % a);
		m = x - u*q;
		n = y - v*q;
		gcd = a;
		a = r;
		x = u;
		y = v;
		u = m;
		v = n;
	}
	return (long long)y;
}


unsigned long long rsa_modExp(unsigned long long a, unsigned long long b, unsigned long long c)
{

	unsigned long long res = 1;
	while (b > 0) {
		/* Need long multiplication else this will overflow... */
		if (b & 1) {
			res = (res * a) % c;
		}
		b = b >> 1;
		a = (a * a) % c; /* Same deal here */
	}
	return res;

}
unsigned int isprime(unsigned int n)
{
	unsigned int flag, i;
	flag = 1;
	for (i = 2; i <= sqrt(n); i++)
	{
		if (n%i == 0)
		{
			flag = 0;
			break;
		}
	}
	return flag;
}

//key replace bit
//key.exponent bit[chg_code[]] <-> key.module bit[chg_code[]]
//
void key_change(key_t *key) {
	unsigned char chg_code[10] = {2,3,5,8,12,17,20,27,28,30};
	unsigned char i;
	unsigned int tmp,offset;
	unsigned int *p = (unsigned int*) key;

	tmp = *p;
	for (i = 0; i < 10; i++) {
		offset = (0x01 << chg_code[i]);

		if ((*(p + 1))&offset)
			*p = *p | offset;
		else
			*p = *p & (~offset);

		if (tmp&offset)
			*(p+1) = *(p+1) | offset;
		else
			*(p + 1) = *(p + 1) & (~offset);

	}
}
void rsa_gen_keys(key_t *pub, key_t *priv)
{

	// choose random primes from the list, store them as p,q
	unsigned int q, p, e;

	long long d;
	unsigned long long r, n;
	//srand((unsigned)time(0));
	// srand((unsigned)GetSystemTime()); wushuai
	static int volatile seed;
    srand((unsigned int)&seed);

	while (1) {
		q = rand() % (0xffff - 0x2000) + 0x2000;
		p = rand() % (0xffff - 0x2000) + 0x2000;
		if (isprime(p) == 0)
			continue;
		else if (isprime(q) == 0)
			continue;
		else if (p == q)
			continue;
		else
			break;
	}
	r = (p - 1)*(q - 1);
	n = p*q;

	while (1) {
		e = rand() % (0x4000000 - 0x1000000) + 0x1000000;
		if (isprime(e) == 0)
			continue;
		else
			break;
	}

	d = ExtEuclid(r, e);
	while (d < 0) {
		d = d + r;
	}

	// We now store the public / private keys in the appropriate structs


	pub->modulus = n;
	pub->exponent = e;

	priv->modulus = n;
	priv->exponent = d;

	key_change(pub);
	key_change(priv);


}

void rsa_encrypt(key_t key, char *mw, int Length, unsigned int *cw)
{
	int i = 0;
	key_change(&key);
	for (i = 0; i<Length; i++)
	{
		cw[i] = rsa_modExp(mw[i], key.exponent, key.modulus);
	//	printf("mingwen:%d = 0x%02x\r\n", i, mw[i]);
	//	printf("miwen:%d = 0x%04x\r\n", i, cw[i]);

	}
}

void rsa_decrypt(key_t key, unsigned int *cw, int Length, char *mw)
{
	int i = 0;
	key_change(&key);
	for (i = 0; i<Length ; ++i)
	{
		mw[i] = rsa_modExp(cw[i], key.exponent, key.modulus);
	}
}

int test_rsa(int len) {
	key_t pub = { 0 };
	key_t priv = { 0 };
	char mv[50] = { 0 };// "abcdefg";
	char mv_t[50] = { 0 };
	unsigned int cw[50];
	int i;

	//generate rand serils num 
	generate_rand(mv, len);
   
	rsa_gen_keys(&pub, &priv);


	rsa_encrypt(priv, mv, len, cw);

	rsa_decrypt(pub, cw, len, mv_t);
	
	for(i=0;i<len;i++)
	{
		if(mv[i]!=mv_t[i])
			return -1;
	}

	return 0;
}

